package com.test.daily.leetcode.y2022.m06.day0614.v01;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/6/14 上午 12:05
 * @version: 1.0
 */
public class Solution {
    public static int dp2(int arr[]){
        int sum = 0;
        int N = arr.length;
        for(int i = 0; i < N; i++){
            sum += arr[i];
        }
        int M = N / 2;
        sum /=2;
        int[][][] dp = new int[N+1][M+1][sum+1];

        for(int i = 0; i <= N; i++){
            for (int j = 0; j <= M; j++) {
                for (int k = 0; k <= sum ; k++) {
                    dp[i][j][k] = -1;
                }
            }
        }
        for(int rest = 0; rest <= M; rest++){
            dp[N][0][rest] = 0;
        }
        for(int index = N - 1; index >= 0; index++){
            for(int count = 0; count <= M; count++){
                for(int rest = 1; rest <= sum; rest++){
                        int p1 = dp[index+1][count][rest];
                        int p2 = -1;
                        int next = -1;
                        if(count -1 >= 0 && rest - arr[index] >=0){
                            next = dp[index+1][count - 1][rest-arr[index]];
                        }
                        if(next >= 0){
                            p2 = next + arr[index];
                        }
                        int ans = Math.max(p1, p2);
                        dp[index][count][rest] = ans;
                }
            }
        }
        return dp[0][M][N];
    }

}
